using System;
using System.Collections.Generic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0739. 每日温度")]
    public class No0739_DailyTemperatures : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Func<int[], int[], bool> fun = (l1, l2) => l1.ToJSONString() == l2.ToJSONString();

            Assert.TestExe(DailyTemperatures,
                new int[] { 73, 74, 75, 71, 69, 72, 76, 73 },
                equalsMethod: fun,
                new int[] { 01, 01, 04, 02, 01, 01, 00, 00 });
            Assert.TestExe(DailyTemperatures,
                new int[] { 89, 62, 70, 58, 47, 47, 46, 76, 100, 70 },
                equalsMethod: fun,
                new int[] { 8, 1, 5, 4, 3, 2, 1, 1, 0, 0 });

            Assert.TestExe(DailyTemperatures2,
                new int[] { 73, 74, 75, 71, 69, 72, 76, 73 },
                equalsMethod: fun,
                new int[] { 01, 01, 04, 02, 01, 01, 00, 00 });
            Assert.TestExe(DailyTemperatures2,
                new int[] { 89, 62, 70, 58, 47, 47, 46, 76, 100, 70 },
                equalsMethod: fun,
                new int[] { 8, 1, 5, 4, 3, 2, 1, 1, 0, 0 });

            Assert.TestExe(DailyTemperatures3,
                new int[] { 73, 74, 75, 71, 69, 72, 76, 73 },
                equalsMethod: fun,
                new int[] { 01, 01, 04, 02, 01, 01, 00, 00 });
            Assert.TestExe(DailyTemperatures3,
                new int[] { 89, 62, 70, 58, 47, 47, 46, 76, 100, 70 },
                equalsMethod: fun,
                new int[] { 8, 1, 5, 4, 3, 2, 1, 1, 0, 0 });
        }


        /// <summary>
        /// 方法一：暴力
        /// </summary>
        public int[] DailyTemperatures(int[] T)
        {
            int len = T.Length;
            int[] result = new int[len];
            int[] next = new int[101];
            for (int i = 0; i < next.Length; i++)
            {
                next[i] = int.MaxValue;
            }
            for (int i = len - 1; i >= 0; i--)
            {
                int warmerIndex = int.MaxValue;
                for (int x = T[i] + 1; x <= 100; x++)
                {
                    if (next[x] < warmerIndex)
                    {
                        warmerIndex = next[x];
                    }
                }

                if (warmerIndex < int.MaxValue)
                {
                    result[i] = warmerIndex - i;
                }
                next[T[i]] = i;
            }
            return result;
        }


        /// <summary>
        /// 方法二：单调栈 列表替代的栈
        /// </summary>
        public int[] DailyTemperatures2(int[] T)
        {
            int len = T.Length;
            int[] result = new int[len];

            List<int> stack = new List<int>();
            for (int i = 0; i < len; i++)
            {
                int temp = T[i];
                while (stack.Count >= 1 && temp > T[stack[stack.Count - 1]])
                {
                    int top_index = stack[stack.Count - 1];
                    stack.RemoveAt(stack.Count - 1);
                    result[top_index] = i - top_index;
                }
                stack.Add(i);
            }
            return result;
        }


        /// <summary>
        /// 方法二：单调栈
        /// </summary>
        public int[] DailyTemperatures3(int[] T)
        {
            int len = T.Length;
            int[] result = new int[len];

            Stack<int> stack = new Stack<int>();
            for (int i = 0; i < len; i++)
            {
                int temp = T[i];
                while (stack.Count >= 1 && temp > T[stack.Peek()])
                {
                    int top_index = stack.Pop();
                    result[top_index] = i - top_index;
                }
                stack.Push(i);
            }
            return result;
        }
    }
}
